home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_pas / pnl002 / linklist.pas next >
Pascal/Delphi Source File  |  1990-05-17  |  7KB  |  226 lines
  1. unit LinkList;
  2.  
  3. { This is the linked list unit accompanying The Pascal NewsLetter, Issue #2.
  4.   This unit is copyrighted by Peter Davis.
  5.   It may be freely distributed in un-modified form, or modified for use in
  6.   your own programs. Programs using any modified or unmodified form of this
  7.   unit must include a run-time and source visible recognition of the author,
  8.   Peter Davis.
  9. }
  10.  
  11. { The DataType used is integer, but may be changed to whatever data type
  12.   that you want.
  13. }
  14.  
  15. interface
  16.  
  17.  
  18. type
  19.   DataType = integer;    { Change this data-type to whatever you want  }
  20.  
  21.   Data_Ptr = ^Data_Rec;  { Pointer to our data records                 }
  22.  
  23.   Data_Rec = record      { Our Data Record format                      }
  24.     OurData  : DataType;
  25.     Next_Rec : Data_Ptr;
  26.   end;
  27.  
  28.  
  29. procedure Init_List(var Head : Data_Ptr);
  30. procedure Insert_Begin(var Head : Data_Ptr; Data_Value : DataType);
  31. procedure Insert_End(var Head : Data_Ptr; Data_Value : DataType);
  32. procedure Insert_In_Order(var Head : Data_Ptr; Data_Value : DataType);
  33. function Pop_First(var Head : Data_Ptr) : DataType;
  34. function Pop_Last(var Head : Data_Ptr) : DataType;
  35. procedure Delete_Here(var Head : Data_Ptr; Our_Rec : Data_Ptr);
  36.  
  37.  
  38.  
  39. implementation
  40.  
  41. procedure Init_List(var Head : Data_Ptr);
  42.  
  43. begin
  44.   Head := nil;
  45. end;
  46.  
  47. procedure Insert_Begin(var Head : Data_Ptr; Data_Value : DataType);
  48.  
  49. { This procedure will insert a link and value into the
  50.   beginning of a linked list.                             }
  51.  
  52. var
  53.   Temp : Data_Ptr;                { Temporary  Pointer.            }
  54.  
  55. begin
  56.   new(Temp);                      { Allocate our space in memory.  }
  57.   Temp^.Next_Rec := Head;         { Point to existing list.        }
  58.   Head:= Temp;                    { Move head to new data item.    }
  59.   Head^.OurData := Data_Value;    { Insert Data_Value.             }
  60. end;
  61.  
  62. procedure Insert_End(var Head : Data_Ptr; Data_Value : DataType);
  63.  
  64. { This procedure will insert a link and value into the
  65.   end of the linked list.                                 }
  66.  
  67. var
  68.   Temp1,             { This is where we're going to put new data }
  69.   Temp2 : Data_Ptr;  { This is to move through the list.         }
  70.  
  71. begin
  72.   new(Temp1);
  73.   Temp2 := Head;
  74.   if Head=nil then
  75.     begin
  76.       Head := Temp1;                  { If list is empty, insert first   }
  77.       Head^.OurData := Data_Value;    { and only record. Add value and   }
  78.       Head^.Next_Rec := nil;          { Then put nil in Next_Rec pointer }
  79.     end
  80.   else
  81.     begin
  82.       { Go to the end of the list. Since Head is a variable parameter,
  83.         we can't move it through the list without losing pointer to the
  84.         beginning of the list. To fix this, we use a third variable:
  85.         Temp2.
  86.       }
  87.       while Temp2^.Next_Rec <> nil do    { Find the end of the list. }
  88.         Temp2 := Temp2^.Next_Rec;
  89.  
  90.       Temp2^.Next_Rec := Temp1;          { Insert as last record.    }
  91.       Temp1^.Next_Rec := nil;            { Put in nil to signify end }
  92.       Temp1^.OurData := Data_Value;      { And, insert the data      }
  93.     end;
  94. end;
  95.  
  96. procedure Insert_In_Order(var Head : Data_Ptr; Data_Value : DataType);
  97.  
  98. { This procedure will search through an ordered linked list, find
  99.   out where the data belongs, and insert it into the list.        }
  100.  
  101. var
  102.   Current,              { Where we are in the list               }
  103.   Next     : Data_Ptr;  { This is what we insert our data into.  }
  104.  
  105. begin
  106.   New(Next);
  107.   Current := Head;      { Start at the top of the list.          }
  108.  
  109.   if Head = Nil then
  110.     begin
  111.       Head:= Next;
  112.       Head^.OurData := Data_Value;
  113.       Head^.Next_Rec := Nil;
  114.     end
  115.   else
  116.   { Check to see if it comes before the first item in the list   }
  117.   if Data_Value < Current^.OurData then
  118.     begin
  119.       Next^.Next_Rec := Head;      { Make the current first come after Next }
  120.       Head := Next;                { This is our new head of the list       }
  121.       Head^.OurData := Data_Value; { And insert our data value.             }
  122.     end
  123.   else
  124.     begin
  125.       { Here we need to go through the list, but always looking one step
  126.         ahead of where we are, so we can maintain the links. The method
  127.         we'll use here is: looking at Current^.Next_Rec^.OurData
  128.         A way to explain that in english is "what is the data pointed to
  129.         by pointer Next_Rec, in the record pointed to by pointer
  130.         current." You may need to run that through your head a few times
  131.         before it clicks, but hearing it in English might make it a bit
  132.         easier for some people to understand.                            }
  133.  
  134.       while (Data_Value >= Current^.Next_Rec^.OurData) and
  135.             (Current^.Next_Rec <> nil) do
  136.         Current := Current^.Next_Rec;
  137.       Next^.OurData := Data_Value;
  138.       Next^.Next_Rec := Current^.Next_Rec;
  139.       Current^.Next_Rec := Next;
  140.     end;
  141. end;
  142.  
  143. function Pop_First(var Head : Data_Ptr) : DataType;
  144.  
  145. { Pops the first item off the list and returns the value to the caller. }
  146.  
  147. var
  148.   Old_Head : Data_Ptr;
  149.  
  150. begin
  151.   If Head <> nil then   { Is list empty? }
  152.     begin
  153.       Old_Head := Head;
  154.       Pop_First := Head^.OurData;  { Nope, so Return the value }
  155.       Head := Head^.Next_Rec;      { And increment head.       }
  156.       Dispose(Old_Head);           { Get rid of the old head.  }
  157.     end
  158.   else
  159.     begin
  160.       writeln('Error: Tried to pop an empty stack!');
  161.       halt(1);
  162.     end;
  163. end;
  164.  
  165.  
  166. function Pop_Last(var Head : Data_Ptr) : DataType;
  167.  
  168. { This function pops the last item off the list and returns the
  169.   value of DataType to the caller.                              }
  170.  
  171. var
  172.   Temp : Data_Ptr;
  173.  
  174. begin
  175.   Temp := Head;       { Start at the beginning of the list. }
  176.   if head = nil then  { Is the list empty? }
  177.     begin
  178.       writeln('Error: Tried to pop an empty stack!');
  179.       halt(1);
  180.     end
  181.   else
  182.   if head^.Next_Rec = Nil then { If there is only one item in list, }
  183.     begin
  184.       Pop_Last := Head^.OurData;  { Return the value               }
  185.       Dispose(Head);              { Return the memory to the heap. }
  186.       Head := Nil;                { And make list empty.           }
  187.     end
  188.   else
  189.     begin
  190.       while Temp^.Next_Rec^.Next_Rec <> nil do  { Otherwise, find the end }
  191.         Temp := Temp^.Next_rec;
  192.       Pop_Last := Temp^.Next_Rec^.OurData;  { Return the value          }
  193.       Dispose(Temp^.Next_Rec);              { Return the memory to heap }
  194.       Temp^.Next_Rec := nil;                { And make new end of list. }
  195.     end;
  196. end;
  197.  
  198.  
  199. procedure Delete_Here(var Head : Data_Ptr; Our_Rec : Data_Ptr);
  200.  
  201.  
  202. { Deletes the node Our_Rec from the list starting at Head. The procedure
  203.   does check for an empty list, but it assumes that Our_Rec IS in the list.
  204. }
  205.  
  206. var
  207.   Current : Data_Ptr;  { Used to move through the list. }
  208.  
  209. begin
  210.   Current := Head;
  211.   if Current = nil then   { Is the list empty? }
  212.     begin
  213.       writeln('Error: Cant delete from an empty stack.');
  214.       halt(1);
  215.     end
  216.   else
  217.     begin   { Go through list until we find the one to delete. }
  218.       while Current^.Next_Rec <> Our_Rec do
  219.         Current := Current^.Next_Rec;
  220.       Current ^.Next_Rec := Our_Rec^.Next_Rec; { Point around old link. }
  221.       Dispose(Our_Rec);                        { Get rid of the link..  }
  222.     end;
  223. end;
  224.  
  225.  
  226. end.